class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        dummyHead = ListNode()
        tmp = dummyHead
        pre = None
        #获取每个节点的前驱节点
        cur = head
        pre_dict = {}
        index = 0
        while cur != None:
            pre_dict[cur] = pre
            pre = cur
            cur = cur.next
        tail = pre
        cur = head
        index = 0
        while cur != tail:
            if index % 2 == 0:
                tmp.next = cur
                tmp = cur
                cur = cur.next
            else:
                tmp.next = tail
                tmp = tail
                tail = pre_dict[tail]
            index += 1
        #奇数个节点时提前退出
        if index % 2 == 0:
            tmp.next = tail
        tail.next = None
        return dummyHead.next
